package LeetCode_88;

import java.util.Arrays;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/10/22 21:52
 * [1,2,3,0,0,0]
 * 3
 * [2,5,6]
 * 3
 */
public class Solution {
    public static void main(String[] args) {
        int[] nums1 = {1,2,3,0,0,0};
        int[] nums2 = {2,5,6};
        merge(nums1,3,nums2,3);
    }
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
//        if (n==0){
//            return;
//        }
//        for (int i = m; i < m+n ; i++) {
//            nums1[i] = nums2[i-m];
//        }
//        Arrays.sort(nums1);
        // end1、end2：分别标记nums1 和 nums2最后一个有效元素位置
        // last标记nums1的末尾，因为nums1和nums2中的元素从后往前往nums1中存放
        // ，否则会存在数据覆盖
        int last = m+n-1;
        int end1 = m-1;
        int end2 = n-1;
        // 从后往前遍历，将num1或者nums2中较大的元素往num1中end位置搬移
        // 直到将num1或者num2中有效元素全部搬移完
        while (end1>=0 && end2 >=0){
            if (nums1[end1] > nums2[end2]){
                nums1[last--] = nums1[end1--];
            }else {
                nums1[last--] = nums2[end2--];
            }
        }
        // 如果nums2中的数据没有搬移完，搬移剩余nums中的元素
        while (end2 >= 0){
            nums1[last--] = nums2[end2--];
        }
        // num1中可能有数据没有搬移完，不用管，因为这些元素已经在nums1中了
    }
}
